package com.clps.algorithm.chapter08.向下的路径结点之和;

import com.clps.algorithm.chapter07.二叉树每层的最大值.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个二叉树和一个值sum，求二叉树里结点值之和等于sum的路径的数目。
 * 路径的定义为二叉树中沿着指向子结点的指针向下移动所经过的结点，但不一定从根结点开始，也不一定到叶结点结束。
 * 例如在图8.5中的二叉树里，有两个路径的结点值之和等于8，其中第一条路径从结点5开始经过结点2到达结点1，第二条路径从结点2开始到结点6。
 */
public class demo01 {
    public static void main(String[] args) {

    }

    public int pathSum(TreeNode root,int sum){
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0,1);
        return dfs(root,sum,map,0);
    }

    private int dfs(TreeNode root, int sum, Map<Integer, Integer> map, int path) {
        if(root == null){
            return 0;
        }

        path +=root.val;

        int count = map.getOrDefault(path-sum,0);
        map.put(path,map.getOrDefault(path,0)+1);

        count+=dfs(root.left,sum,map,path);
        count+=dfs(root.right,sum,map,path);

        map.put(path,map.get(path)-1);

        return count;
    }
}
